In Japanese Patent No. 4211794, an apparatus configured to generate a travel trajectory avoiding a contact with an object around the vehicle is disclosed. The apparatus sequentially moves each position of the vehicle and the object around the vehicle in micro-step (for example, 0.1 to 0.5 second), and calculates a degree of interference between the vehicle and the object for each micro-step. The apparatus determines the travel trajectory of the vehicle based on a result of evaluation.